Masala #R109C

Bahor kelishi bilan bog‘bon o‘z bog‘ida olma daraxti ko‘chatlarini parvarish qilishni boshladi. Qulaylik uchun bog‘ni \(1\) dan \(N\) gacha raqamlangan uzun chiziq deb qaraylik. Har bir \(i\) nuqtada bitta ko‘chat bor.

Boshlanishida barcha ko‘chatlarning bo‘yi \(0\) sm.

Bog‘bon har kuni bitta sug‘orish ishini bajaradi. Bunda u istalgan \([L,R]\) oraliqni tanlaydi \(1≤L≤R≤N)\) va shu oraliqdagi barcha ko‘chatlarning bo‘yini \(1\) sm ga o'sadi. 

Bog‘bon \(i-\) ko‘chatning yakuniy bo‘yi aynan \(h_i\)​ sm bo‘lishini xohlaydi. Sizning vazifangiz, barcha ko‘chatlarni aynan kerakli balandlikka yetkazish uchun zarur bo‘lgan eng kam kunlar sonini topish.

Birinchi qatorda bitta butun son \(N (1 \le N \le 10^5)\) - bog'dagi daraxtlar soni kiritiladi. 

Keyingi qatorda \(N\) ta butun son \(h_i (0 \le h_i \le 10^9)\) - har bir daraxtning bog'bon xohlagan balandligi kiritiladi.

Bitta butun son chiqaring, barcha ko‘chatlarni \(h_i\)​ balandliklarga yetkazish uchun kerak bo‘ladigan eng kam sug‘orish kunlari soni.